using System;
using System.Collections.Generic;

namespace LannyPractiseCode.Shu
{
    public class HeapSort
    {
        public static void HeapSortHelper(int[] arrs)
        {
            int temp=0;
            //分布完成
            //AdjustHeap(arrs,1,arrs.Length);//第一次
            //AdjustHeap(arrs,0,arrs.Length);//第二次，注意：arrs.Length，第二次才完成把最大的放到顶上
            //所以，得到下面的：
            for (int i = arrs.Length/2-1; i >=0; i--)
            {
                AdjustHeap(arrs,i,arrs.Length);
            }

            //将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端
            //重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
            for (int i = arrs.Length-1; i >0; i--)
            {
                //交换
                temp=arrs[i];
                arrs[i]=arrs[0];
                arrs[0]=temp;
                AdjustHeap(arrs,0,i);

            }

            System.Console.WriteLine(string.Join(",",arrs));
        }
        /// <summary>
        /// 完成将以i对于的非叶子节点的树调整成大顶堆
        /// </summary>
        /// <param name="arr[]">待调整的数组</param>
        /// <param name="i">i表示非叶子节点子数组的索引</param>
        /// <param name="length">表示对多少个元素继续调整，length实在逐渐的减少</param>
        public static void AdjustHeap(int[] arr,int i,int length)
        {
            int temp=arr[i];//先取出当前元素的值，保存在临时变量中

            //开始调整
            //k=i*2+1，k是i结点的左子树结点
            //k=k*2+1,确定当前子树的左子树节点
            for (int k = i*2+1; k < length; k=k*2+1)
            {
                if(k+1<length && arr[k]<arr[k+1])//左子树结点的值小于右子树结点的值
                {
                    k++;//k+1，指向右子树
                }
                //这个时候 k指向了最大的值中
                if(arr[k]>temp)//如果子结点，大于父结点
                {
                    arr[i]=arr[k];//把较大的值赋值给当前结点
                    i=k;//!!!!i指向k，继续循环比较...
                }
                else{
                    break;
                }
            }
            //当for 循环结束后，我们已经将以i为父节点的树的最大值，放在了最顶（局部）
            arr[i]=temp;
        }
    }
}